package com.acwing.partition2;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;

/**
 * @author `RKC`
 * @date 2022/1/4 9:02
 */
public class AC171送礼物 {

    private static final int N = 46;
    private static final int[] w = new int[N];
    private static int answer = 0, m = 0, n = 0, mid = 0;
    private static final TreeSet<Long> set = new TreeSet<>();

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        m = Integer.parseInt(s[0]);
        n = Integer.parseInt(s[1]);
        for (int i = 0; i < n; i++) w[i] = Integer.parseInt(reader.readLine());
        //优化搜索顺序
        Arrays.sort(w, 0, n);
        for (int i = 0; i < n / 2; i++) {
            int temp = w[i];
            w[i] = w[n - i - 1];
            w[n - i - 1] = temp;
        }
        //先对前半部分进行搜索，得到任意个物品组合后的重量
        mid = n / 2 + 2;
        dfs1(0, 0);
        //Set集合已经对组合后的元素进行了去重和排序了，枚举后半物品的任意组合，在枚举过程中使用二分查找dfs1中的打表结果。整个过程有点两数之和的思想
        dfs2(mid, 0);
        writer.write(answer + "\n");
        writer.flush();
    }

    private static void dfs1(int u, long s) {
        set.add(s);
        if (u >= mid) return;
        //每个物品有两种情况，要么选，要么不选
        if (s + w[u] <= m) dfs1(u + 1, s + w[u]);
        dfs1(u + 1, s);
    }

    private static void dfs2(int u, long s) {
        if (u >= n) {
            //二分查找比(m-s)小的最大的数，可以直接调用TreeSet的lower，也可以手写二分，但需要使用线性表，而不是TreeSet
            long res = set.contains(m - s) ? m - s : set.lower(m - s);
            answer = (int) Math.max(answer, res + s);
            return;
        }
        if (s + w[u] <= m) dfs2(u + 1, s + w[u]);
        dfs2(u + 1, s);
    }
}
